1734D - Slime Escape - CodeForces Solution


data structures dp greedy two pointers *1800

Please click on ads to support us..

Python Code:

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    r = k
    k -= 1
    l = k - 1
    x = y = 0
    mr = ml = 0
    while l >= 0 and r < n:
        if l >= 0  and (a[k] + a[l] + x + mr >= 0):
            x += a[l]
            ml = max(x, ml)
            l -= 1
        elif r < n and (a[k] + a[r] + y + ml >= 0):
            y += a[r]
            mr = max(y, mr)
            r += 1
        else:
            break
 
    if l == -1 or r == n:
        print("YES")
    else:
        print("NO")

C++ Code:

// Hi
#include <bits/stdc++.h>
#define f(i, n) for (int i = 0; i < n; i++)
#define f1(i, n) for (int i = 1; i <= n; i++)
#define fn(i, j, k) for (int i = j; i <= k; i++)
#define maan  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define MOD 1000000007

using namespace std;

// void maan() 
// {
//   
//   #ifndef ONLINE_JUDGE
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
//   #endif 
// }

void solve()
{
  ll p,q;cin>>p>>q;
  ll b[p];
  f(i,p) cin>>b[i];
  vector<ll>v(p+1,0);
  f(i,p) v[i+1]=b[i]+v[i];
  ll i=q-1,j=q,c1=v[q-1],c2=v[q];
  while (i>0 && j<p)
  {
    if (c1<=v[j+1]) c2=max(c2,v[j+1]),j+=1;
    else if (c2>=v[i-1]) c1=min(c1,v[i-1]),i-=1;
    else break;
  }
  if (i>0 && j<p) cout<<"NO\n";
  else cout<<"YES\n";

  return;
}

int main()
{
  maan
  int r;cin>>r;while (r--)
  {
    solve();
  }

  return 0;
}
/*
6
7 4
-1 -2 -3 6 -2 -3 -1
3 1
232 -500 -700
7 4
-1 -2 -4 6 -2 -4 -1
8 4
-100 10 -7 6 -2 -3 6 -10
8 2
-999 0 -2 3 4 5 6 7
7 3
7 3 3 4 2 1 1

*/


Comments

Submit
0 Comments
More Questions

479A - Expression
1480A - Yet Another String Game
1216C - White Sheet
1648A - Weird Sum
427A - Police Recruits
535A - Tavas and Nafas
581A - Vasya the Hipster
1537B - Bad Boy
1406B - Maximum Product
507B - Amr and Pins
379A - New Year Candles
1154A - Restoring Three Numbers
750A - New Year and Hurry
705A - Hulk
492B - Vanya and Lanterns
1374C - Move Brackets
1476A - K-divisible Sum
1333A - Little Artem
432D - Prefixes and Suffixes
486A - Calculating Function
1373B - 01 Game
1187A - Stickers and Toys
313B - Ilya and Queries
579A - Raising Bacteria
723A - The New Year Meeting Friends
302A - Eugeny and Array
1638B - Odd Swap Sort
1370C - Number Game
1206B - Make Product Equal One
131A - cAPS lOCK